import java.util.*;
public class NRU{


LinkedList<String> list;
NRUNode[] pageTable;
int clockPeriod=0,clockPeriodCounter=0,pageFaultCounter=0;
Scanner scanner;
boolean inRam=false,freeRamSlot=false;
	public NRU(LinkedList<String> list,int clockPeriod,int numberOfFrames){
		pageTable= new NRUNode[numberOfFrames];
		this.list=list;
		this.clockPeriod=clockPeriod;
		System.out.println("Applying NRU for page replacement");
		System.out.println("RAM="+numberOfFrames+" page frames");
		System.out.println("Clock Period= "+clockPeriod+" page references");
		for(int i=0; i<pageTable.length;i++){
			pageTable[i]=new NRUNode();
		}
		
		for(int i=1;i<list.size(); i++){
			
			String command = list.get(i);
			scanner=new Scanner(command);
			String letter=scanner.next();
			int pageNumber=scanner.nextInt();
			
			int pageLocation=inRam(pageNumber);///check to see if the page is in ram
			if(pageLocation!=-1){
				System.out.println(letter+" "+pageNumber+ ": in RAM");
				//if this is a write instruction we change the modified bit to one
				if(letter.charAt(0)=='W')pageTable[pageLocation].modifiedBit=1;
				else pageTable[pageLocation].refereceBit=1;
			}
			else{//the page is not in add the page to memory and generate a page fault
				int openSlot=findOpenSlot();
				if(openSlot!=-1){//there is an available spot in memory;
				pageTable[openSlot].pageNumber=pageNumber;
				if(letter.charAt(0)=='W')pageTable[openSlot].modifiedBit=1;
				System.out.println(letter+" "+pageNumber+ ": page fault");
				pageFaultCounter++;//count the number of page faults
				}
				else{//there is no space and a psge must be evicted!
					int pageToEvict=findPageToEvict();
					int temp=pageTable[pageToEvict].pageNumber;
					pageTable[pageToEvict]=new NRUNode();
					pageTable[pageToEvict].pageNumber=pageNumber;
					if(letter.charAt(0)=='W')pageTable[pageToEvict].modifiedBit=1;
					System.out.println(letter+" "+pageNumber+ ": page fault");
					pageFaultCounter++;//count the number of page faults
					System.out.println("  page "+temp +" evicted!");
				}
			}
			clockPeriodCounter++;
			if(clockPeriodCounter==clockPeriod){
				clockPeriodCounter=0;
				System.out.println("<<<Time to clear R bits>>>");
				for(int index=0;index<pageTable.length;index++){
				pageTable[index].refereceBit=0;	
				}
			}
		}
		System.out.println("Total number of page faults: "+pageFaultCounter);
	}

	
	
	public int inRam(int pageNumber){//check to see if the page is in ram
		for(int i=0;i<pageTable.length;i++){
			if(pageTable[i].pageNumber==pageNumber)return i;
		}
		return -1;
	}
	
	public int findOpenSlot(){
		for (int i=0;i<pageTable.length;i++){
			if(pageTable[i].pageNumber==-1)return i;
		}
		return -1;
	}
	public int findPageToEvict(){
		
		switch(1){
		case 1:		for(int i=0; i<pageTable.length;i++){
						if(pageTable[i].refereceBit==0&&pageTable[i].modifiedBit==0){
							return i;
						}
					}
		case 2:		for(int i=0; i<pageTable.length;i++){
						if(pageTable[i].refereceBit==0&&pageTable[i].modifiedBit==1){
							return i;
						}
					}	
		
		case 3:		for(int i=0; i<pageTable.length;i++){
						if(pageTable[i].refereceBit==1&&pageTable[i].modifiedBit==0){
							return i;
						}
					}
		
		
		case 4:		for(int i=0; i<pageTable.length;i++){
						if(pageTable[i].refereceBit==1&&pageTable[i].modifiedBit==1){
							return i;
						}
					}
			
		}
		
		return 0;
	}

}